package com.interview.javabase.algorithm;

/**
 * @description:
 * @author: zhangshuguang@vichain.com
 * @date: 2019/09/29 10:53
 */
public class BinarySortTree {

    public static void main(String[] args) {
        BinarySortTree binarySortTree = new BinarySortTree();
        int[] arr = {1, 9, 5, 6, 5, 2, 3, 6, 58, 7, 4};
        for (int i = 0; i < arr.length; i++) {
            int i1 = arr[i];
            binarySortTree.add(new TreeNode(i1));
        }

//        binarySortTree.infixOrder();

//        TreeNode treeNode = binarySortTree.findTreeNode(new TreeNode(5));
//        System.out.println(treeNode);
//        TreeNode parentTreeNode = binarySortTree.findParentTreeNode(new TreeNode(5));
//        System.out.println(parentTreeNode);

//        TreeNode minTreeNode = binarySortTree.findMinTreeNode(treeNode);
//        System.out.println(minTreeNode);

        binarySortTree.deleteTreeNode(new TreeNode(1));

        binarySortTree.infixOrder();
    }

    private TreeNode root;

    public void add(TreeNode treeNode) {
        if (this.root == null) {
            this.root = treeNode;
        } else {
            this.root.add(treeNode);
        }
    }


    public TreeNode findTreeNode(TreeNode treeNode) {
        if (this.root != null) {
            return this.root.findTreeNode(treeNode);
        }

        return null;
    }

    public void deleteTreeNode(TreeNode targetNode) {

        if (root.left == null && root.right == null) {
            root = null;
            return;
        }

        if (targetNode == null) {
            return;
        }

        // 查找需要删除的子树
        TreeNode treeNode = this.findTreeNode(targetNode);
        if (treeNode == null) {
            System.out.println("查找的数据不存在");
            return;
        }

        TreeNode treeNodeParent = this.root.findTreeNodeParent(targetNode);

        // 1. 删除的节点为叶子节点
        if (treeNode.right == null && treeNode.left == null) {
            if (treeNodeParent.left != null && treeNodeParent.left == treeNode) {
                treeNodeParent.left = null;
            } else {
                treeNodeParent.right = null;
            }

        } else if (treeNode.right == null || treeNode.left == null) {
            // 2. 删除的节点有一颗子树
            if (treeNode.right != null) {
                if (treeNodeParent == null) {
                    root = treeNode.right;
                } else if (treeNodeParent.left != null && treeNodeParent.left == treeNode) {
                    treeNodeParent.left = treeNode.right;
                } else {
                    treeNodeParent.right = treeNode.right;
                }
            } else {
                if (treeNodeParent == null) {
                    root = treeNode.left;
                } else if (treeNodeParent.left != null && treeNodeParent.left == treeNode) {
                    treeNodeParent.left = treeNode.left;
                } else {
                    treeNodeParent.right = treeNode.left;
                }
            }
        } else {
            // 3. 删除的节点有两颗子树
            // 查找右子树最小的节点
            TreeNode minTreeNode = treeNode.right.findMinTreeNode();
            treeNode.value = minTreeNode.value;
        }
    }

    public TreeNode findParentTreeNode(TreeNode treeNode) {
        if (this.root != null) {
            return this.root.findTreeNodeParent(treeNode);
        }

        return null;
    }

    // 查询最小的节点
    public TreeNode findMinTreeNode(TreeNode treeNode) {

        return treeNode.right.findMinTreeNode();
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        }
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("TreeNode{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }

    public void deleteNode(TreeNode targetNode) {
        if (targetNode == null) {
            return;
        }

        // 查找需要删除的子树
        TreeNode treeNode = this.findTreeNode(targetNode);
        if (treeNode == null) {
            System.out.println("查找的数据不存在");
            return;
        }

        TreeNode treeNodeParent = this.findTreeNodeParent(targetNode);

        // 1. 删除的节点为叶子节点
        if (treeNode.right == null && treeNode.left == null) {
            if (treeNodeParent.left != null && treeNodeParent.left == treeNode) {
                treeNodeParent.left = null;
            } else {
                treeNodeParent.right = null;
            }

        } else if (treeNode.right == null || treeNode.left == null) {
            // 2. 删除的节点有一颗子树
            if (treeNode.right != null) {
                if (treeNodeParent == null) {
                    TreeNode root = this;
                    root = treeNode.right;
                } else if (treeNodeParent.left != null && treeNodeParent.left == treeNode) {
                    treeNodeParent.left = treeNode.right;
                } else {
                    treeNodeParent.right = treeNode.right;
                }
            } else {
                if (treeNodeParent == null) {
                    TreeNode root = this;
                    root = treeNode.left;
                } else if (treeNodeParent.left != null && treeNodeParent.left == treeNode) {
                    treeNodeParent.left = treeNode.left;
                } else {
                    treeNodeParent.right = treeNode.left;
                }
            }
        } else {
            // 3. 删除的节点有两颗子树
            // 查找右子树最小的节点
            TreeNode minTreeNode = treeNode.right.findMinTreeNode();
            treeNode.value = minTreeNode.value;
        }
    }

    // 查询最小的节点
    public TreeNode findMinTreeNode() {

        if (this.left == null) {
            deleteNode(this);
            return this;
        }

        return this.left.findMinTreeNode();
    }

    /**
     * 添加节点
     * @param treeNode
     */
    public void add(TreeNode treeNode) {

        if (treeNode == null) {
            return;
        }

        if (treeNode.value < this.value) {
            if (this.left == null) {
                this.left = treeNode;
            } else {
                this.left.add(treeNode);
            }
        } else {
            if (this.right == null) {
                this.right = treeNode;
            } else {
                this.right.add(treeNode);
            }
        }
    }

    /**
     * 查找值
     */
    public TreeNode findTreeNode(TreeNode treeNode) {

        if (treeNode == null) {
            return null;
        }

        if (treeNode.value < this.value) {
            return this.left.findTreeNode(treeNode);
        }

        if (treeNode.value > this.value) {
            return this.right.findTreeNode(treeNode);
        }

        if (this.value == treeNode.value) {
            return this;
        }

        return null;
    }

    /**
     * 查找值
     */
    public TreeNode findTreeNodeParent(TreeNode treeNode) {

        if ((this.left != null && this.left.value == treeNode.value) || this.right != null && this.right.value == treeNode.value) {
            return this;
        } else {
            if (this.left != null) {
                return this.left.findTreeNodeParent(treeNode);
            } else if (this.right != null) {
                return this.right.findTreeNodeParent(treeNode);
            } else {
                return null;
            }
        }

    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }

        System.out.println(this);

        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}
